{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Destination City"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #hash-table #string"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #哈希表 #字符串"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: destCity"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #旅行终点站"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一份旅游线路图，该线路图中的旅行线路用数组 <code>paths</code> 表示，其中 <code>paths[i] = [cityA<sub>i</sub>, cityB<sub>i</sub>]</code> 表示该线路将会从 <code>cityA<sub>i</sub></code> 直接前往 <code>cityB<sub>i</sub></code> 。请你找出这次旅行的终点站，即没有任何可以通往其他城市的线路的城市<em>。</em></p>\n",
    "\n",
    "<p>题目数据保证线路图会形成一条不存在循环的线路，因此恰有一个旅行终点站。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>paths = [[\"London\",\"New York\"],[\"New York\",\"Lima\"],[\"Lima\",\"Sao Paulo\"]]\n",
    "<strong>输出：</strong>\"Sao Paulo\" \n",
    "<strong>解释：</strong>从 \"London\" 出发，最后抵达终点站 \"Sao Paulo\" 。本次旅行的路线是 \"London\" -&gt; \"New York\" -&gt; \"Lima\" -&gt; \"Sao Paulo\" 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>paths = [[\"B\",\"C\"],[\"D\",\"B\"],[\"C\",\"A\"]]\n",
    "<strong>输出：</strong>\"A\"\n",
    "<strong>解释：</strong>所有可能的线路是：\n",
    "\"D\" -&gt; \"B\" -&gt; \"C\" -&gt; \"A\".&nbsp;\n",
    "\"B\" -&gt; \"C\" -&gt; \"A\".&nbsp;\n",
    "\"C\" -&gt; \"A\".&nbsp;\n",
    "\"A\".&nbsp;\n",
    "显然，旅行终点站是 \"A\" 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>paths = [[\"A\",\"Z\"]]\n",
    "<strong>输出：</strong>\"Z\"\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= paths.length &lt;= 100</code></li>\n",
    "\t<li><code>paths[i].length == 2</code></li>\n",
    "\t<li><code>1 &lt;=&nbsp;cityA<sub>i</sub>.length,&nbsp;cityB<sub>i</sub>.length &lt;= 10</code></li>\n",
    "\t<li><code>cityA<sub>i&nbsp;</sub>!=&nbsp;cityB<sub>i</sub></code></li>\n",
    "\t<li>所有字符串均由大小写英文字母和空格字符组成。</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [destination-city](https://leetcode.cn/problems/destination-city/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [destination-city](https://leetcode.cn/problems/destination-city/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[\"London\",\"New York\"],[\"New York\",\"Lima\"],[\"Lima\",\"Sao Paulo\"]]', '[[\"B\",\"C\"],[\"D\",\"B\"],[\"C\",\"A\"]]', '[[\"A\",\"Z\"]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def destCity(self, paths: List[List[str]]) -> str:\n",
    "        s, e = set(), set()\n",
    "        for i in range(len(paths)):\n",
    "            s.add(paths[i][0])\n",
    "            e.add(paths[i][1])\n",
    "        for i in e:\n",
    "            if i not in s:\n",
    "                return i\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def destCity(self, paths: List[List[str]]) -> str:\n",
    "        return (set(p[1] for p in paths)-set(p[0] for p in paths)).pop()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def destCity(self, paths: List[List[str]]) -> str:\n",
    "        tail_set, head_set = set(), set()\n",
    "        for i in paths:\n",
    "            head_set.add(i[0])\n",
    "            tail_set.add(i[1])\n",
    "        return (tail_set - head_set).pop()\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def destCity(self, paths: List[List[str]]) -> str:\n",
    "        return (set(p[1] for p in paths) - set(p[0] for p in paths)).pop()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def destCity(self, paths: List[List[str]]) -> str:\n",
    "        start=[]\n",
    "        for i in  paths:\n",
    "            start.append(i[0])\n",
    "        for j in paths:\n",
    "            if j[1] not in start:\n",
    "                return j[1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\r\n",
    "\r\n",
    "\r\n",
    "class Solution:\r\n",
    "    def destCity(self, paths: List[List[str]]) -> str:\r\n",
    "        class Node():\r\n",
    "            def __init__(self):\r\n",
    "                self.nexts = []\r\n",
    "        \r\n",
    "        dic = {}\r\n",
    "        for path in paths:\r\n",
    "            for site in path:\r\n",
    "                if site not in dic:\r\n",
    "                    dic[site] = Node()\r\n",
    "            dic[path[0]].nexts.append(path[1])\r\n",
    "        \r\n",
    "        for city in dic:\r\n",
    "            if not dic[city].nexts:\r\n",
    "                return city\r\n",
    "        return None"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def destCity(self, paths: List[List[str]]) -> str:\n",
    "\n",
    "        # 直接考虑深度优先遍历\n",
    "\n",
    "        # 将路线转换成图\n",
    "        graph = collections.defaultdict()\n",
    "        graph = {}\n",
    "        for i in paths:\n",
    "            graph[i[0]] = i[1]\n",
    "\n",
    "        res = \"\"\n",
    "        def recur(a):\n",
    "            nonlocal res\n",
    "            # 递归停止条件\n",
    "            if a not in graph:\n",
    "                res = a\n",
    "                return \n",
    "\n",
    "            # 找下一个节点\n",
    "            recur(graph[a])\n",
    "        \n",
    "        recur(paths[0][0])\n",
    "        \n",
    "        return res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def destCity(self, paths: List[List[str]]) -> str:\n",
    "         start, end = [], []\n",
    "         for s, e in paths:\n",
    "              start.append(s)\n",
    "              end.append(e)\n",
    "              \n",
    "         for x in end:\n",
    "              if x not in start:\n",
    "                  return x"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def destCity(self, paths: List[List[str]]) -> str:\n",
    "        if len(paths) == 1:\n",
    "            return paths[0][1]\n",
    "        lx, lp = [], []\n",
    "        for path in paths:\n",
    "            x,p = path[0],path[1]\n",
    "            lx.append(x)\n",
    "            lp.append(p)\n",
    "        for i in lp:\n",
    "            if i not in lx:\n",
    "                return i\n",
    "            \n",
    "            \n",
    " \n",
    "                \n",
    "                    \n",
    "            \n",
    "\n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def destCity(self, paths: List[List[str]]) -> str:\n",
    "        list = []\n",
    "        for i in paths:\n",
    "            for j in i:\n",
    "                list.append(j)\n",
    "        new_list = set(list)\n",
    "        for i in new_list:\n",
    "            count = list.count(i)\n",
    "            if count == 1 and (list.index(i)) % 2 != 0:\n",
    "                return i"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def destCity(self, paths: List[List[str]]) -> str:\n",
    "        # 1.set\n",
    "        beginCity = set()\n",
    "        endCity = set()\n",
    "        for path in paths:\n",
    "            beginCity.add(path[0])\n",
    "            endCity.add(path[1])\n",
    "        return (endCity - beginCity).pop()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "\n",
    "class Solution:\n",
    "    def destCity(self, paths: List[List[str]]) -> str:\n",
    "        edges = defaultdict(list)\n",
    "        start = paths[0][0]\n",
    "        for fr, to in paths:\n",
    "            edges[fr].append(to)\n",
    "\n",
    "        result = None\n",
    "        def dfs(node):\n",
    "            nonlocal result\n",
    "            if len(edges[node]) == 0:\n",
    "                result = node\n",
    "                return\n",
    "            for reach in edges[node]:\n",
    "                dfs(reach)\n",
    "\n",
    "        dfs(start)\n",
    "        return result\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def destCity(self, paths: List[List[str]]) -> str:\n",
    "        # 要求输出终点，终点必定是列表最右侧的元素\n",
    "        # 所有的起点作为集合a，\n",
    "        # 所有的终点作为集合b，\n",
    "        # (b-a).pop 弹出集合最后一个元素\n",
    "        begincity = set()\n",
    "        arrivcity = set()\n",
    "        for path in paths:\n",
    "            begincity.add(path[0])\n",
    "            arrivcity.add(path[1])\n",
    "        \n",
    "        return (arrivcity-begincity).pop() "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def destCity(self, p: List[List[str]]) -> str:\n",
    "        dc={}\n",
    "        for i,v in p:\n",
    "            dc[i]=v\n",
    "        for i in dc.keys():\n",
    "            v=dc[i]\n",
    "            if v not in dc.keys():\n",
    "                return v"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def destCity(self, paths: List[List[str]]) -> str:\n",
    "        a = set()\n",
    "        b = set()\n",
    "        for e in paths:\n",
    "            a.add(e[0])\n",
    "            b.add(e[1])\n",
    "        return (b-a).pop()"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
